//
// AVL Tree
// Created by ubuntu on 22-12-7.
//

#ifndef C_DATA_STRUCTURE_AVL_TREE_H
#define C_DATA_STRUCTURE_AVL_TREE_H

typedef int ElemType;

typedef struct BiTNode {
    ElemType data;
    int height;
    struct BiTNode *lchild, *rchild;

    BiTNode() : data(0), height(0), lchild(nullptr), rchild(nullptr) {}

    BiTNode(ElemType x) : data(x), height(0), lchild(nullptr), rchild(nullptr) {}
} BiTNode, *BiTree;


bool InitBiTree(BiTree &T); //初始化
BiTNode *Search(BiTNode *root, const ElemType &data);   //二叉搜索树的查找
bool Insert(BiTNode *&root, const ElemType &data);  //二叉搜索树的插入
bool Remove(BiTNode *&root, const ElemType &data);  //二叉搜索树的删除

//遍历相关
void visit(BiTNode *p);     //打印节点信息
void PreOrder_Rec(BiTree T);    //先序遍历（递归）
void InOrder_Rec(BiTree T);     //中序遍历（递归）
void PostOrder_Rec(BiTree T);   //后序遍历（递归）
void PostOrder(BiTree T);   //后序遍历（栈）
void InOrder(BiTree T);     //先序遍历（栈）
void PreOrder(BiTree T);    //前序遍历（栈）
void LevelOrder(BiTree T);  //层序遍历（队列）
#endif //C_DATA_STRUCTURE_AVL_TREE_H
